package greed;

import java.util.Arrays;
import java.util.Comparator;

/**
 * @Classname : MinimumNumberOfArrowsToBurstBalloons
 * @Description : 452. 用最少数量的箭引爆气球
 * https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
 * @Author : chentianyu
 * @Date 2023/2/24 00:06
 */


public class MinimumNumberOfArrowsToBurstBalloons {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (o1, o2)->Integer.compare(o1[1], o2[1]));
        int ans = 0, right = points[0][1];
        for (int i=1; i<points.length; i++) {
            if (points[i][0] <= right) ans++;
            else right = points[i][1];
        }
        // 总区间减去重叠的区间就是剩余独立的区间，即最少的箭数
        return points.length - ans;
    }
}
